This invention relates generally to a method and apparatus for improving the appearance of printed documents, and more particularly to the efficient use of template rotation within a template matching process for the enhancement of digital images.
Information systems for handling numerous document and data formats are moving towards becoming open systems where different devices are tied to one another to provide solutions to customers"" needs. A key factor in such open systems is enabling an electronic document to be printed so that the customer does not perceive any difference between versions printed on different output devices. In order to achieve complete device-independence, efficient methods of accurately altering image resolution and enhancement are required to take advantage of the technology. Hence, raster conversion technology, where a bitmap created for a first output device is altered so as to be printable on a second output device, has become an important aspect of the open system technology.
Another important aspect is the preservation of the investment in technologies, while improving printers and print appearances. A common example for this case is the storage of fonts, forms, etc. in the form of bitmaps at a specified resolution, say 300xc3x97300 spots per inch (spi). With improving print engines, output resolutions of 600xc3x97600 spi, 300xc3x971200 spi and the like are possible. However, existing applications using, for example, 300xc3x97300 spi fonts have to be handled by these new output devices at a quality level that exceeds that of the 300xc3x97300 spi output devices.
The present invention is a method and apparatus for efficiently processing digital image data to produce enhanced output images. Generally speaking, the invention employs resolution enhancement filters in the form of templates in look-up tables or logic operations. The invention may be used in design and implementation processes of template matching applications available in the art. Such applications include, but are not limited to resolution enhancement, appearance tuning, appearance matching, conversion to gray-scale (e.g., halftone de-screening), image restoration, pattern detection and segmentation.
Enhancement filters operate on image bitmaps to improve document appearance by converting from an original resolution to an output resolution of the printing or display device, at an integer multiple in each direction of the input resolution. The resulting image signals may then be used to drive devices at the output resolution without negatively impacting spatially sensitive features within the input image. In one embodiment, the present invention associates individual templates with multiple-bit per pixel, statistically generated look-up tables to reduce the number of look up tables that is required to improve the appearance of reproduced document images. The invention includes a technique for rotating templates about an axis, and using the original and flipped templates with a single multiple bit per pixel look up table to generate output signals that accurately represent the original image. The generated pixel image signals may then be used to drive output devices with higher fast-scan resolution or with output devices capable of printing multiple-bit per pixel output.
The present invention may be utilized to control a scanning beam where the beam varies in intensity and duration according to the pulses used to control it. For example, a laser beam may be used in a printer for selectively exposing areas on a photoreceptor. The latent electrostatic image formed on the photoreceptor by the beam exposure attracts developing toner, in proportion to the latent image charge level, to develop the image. As another example, a cathode ray tube uses an electron beam to scan a phosphorous screen. The electron beam may be varied in intensity and duration to accurately display information on the phosphor screen. In both examples, a pulse forming circuit responsive to the multiple-bit per pixel image signal may be used to generate video pulses to control the intensity and operation time of the respective beams.
In the preferred embodiment, the present invention will be used to efficiently implement template matching filters. These template matching filters will be designed by any of a number of methods, including but not limited to calculations that are based on geometry, statistics and expert knowledge of specific pattern shapes. One important aspect of the present invention allows multiple template filters that are intended for different portions of a pixel enhancement to be reduced to a single (or reduced number of) filter which may then be applied using efficient symmetry determination as disclosed in the present invention. For instance, in converting an image from a resolution of 300 spi to 600 spi, a single template matching filter could be used at various symmetries and each symmetry would generate one pixel of the four high resolution image pixels that is substituted for each input pixel.
In another aspect of the present invention, filtering may be applied to achieve a pixel that is not necessarily spatially divided into higher resolution sample. For example, such a filter may be used for activating or deactivating binary pixels in operations for enhancement operations such as thickening, thinning, or restoration. Yet another aspect of the present invention is use in converting binary pixels to gray-scale, as in the case of halftone de-screening, as well as in some forms of restoration and anti-aliasing. The present invention would efficiently implement multiple symmetries of a pattern as a single pattern within the template look-up table.
Still another aspect of the present invention may be used to enhance the design of template matching filters. The invention allows for more accurate statistical design by pooling data acquired that has been acquired for multiple symmetries of a pattern into the statistics of a single (or reduced number) of representative patterns. Those skilled in the art will recognize that the invention may be adapted for use with other filter design methods. For example, one member of a symmetry may be designed and the other templates may be derived from that designed pattern.
Previously, various methods and apparatus have been used to improve the quality of a reproduced image by using a template matching scheme in conjunction with a look up table. The following disclosures may be relevant to aspects of the invention:
U.S. Pat. No. 4,437,122 to Walsh et al. teaches an improved method of converting low resolution images into images of higher resolution for printing so as to simultaneously increase density and smooth character edges. In a CRT display or hardcopy output apparatus, the invention is accomplished by converting an original pixel into a higher resolution 3xc3x973 enhanced representation. The status of each of the nine elements in the enhanced representation is determined as a result of an examination of the neighboring pixels of the original pixel.
U.S. Pat. No. 4,847,641 and U.S. Pat. No. 5,005,139 to Tung disclose print enhancement circuitry for a laser beam printer. The bit map of a region of the image to be output is compared to a number of patterns or templates. When a match is detected, a section of the bitmap that was matched is replaced with a unique bitmap section designed to compensate for errors. The replacement bitmap section may include predetermined shifting of some dot positions to compensate for the error in the original bitmap section.
U.S. Pat. No. 4,933,689 to Yoknis describes a method for enhancing a displayed image in a laser exposed dot matrix format to produce softened edge contours. Using three pulses, a central pulse plus leading and trailing enhancement pulses that are separated therefrom. The purpose of the leading and trailing pulses is to create a blurred or grayed region at the leading and trailing edges of each associated character.
U.S. Pat. No. 5,237,646 to Bunce discloses a method for enhancing reproduction of pixel images includes the steps of: storing a raster scan bit map of an image; selecting an input window from the bit map image that includes a plurality of row segments of bits representing pixels, the input window having a center pixel bit; comparing a subset of bits in the input window (that includes the center pixel bit) with a plurality of prediction bit subsets, each prediction subset represented in a plurality of rotation orientations, and upon finding a match with one of the prediction bit subsets, rotating the input window to the degree and direction indicated by a command associated with a matching prediction subset (if any); comparing the rotated input window with a limited set of sample windows to determine a match of certain bit states within the rotated input window with certain bits of a stored sample window; and upon determining that such a match exists, substituting an enhanced pixel representation for the center pixel bit of the input window.
U.S. Pat. No. 5,383,036 to Mailloux et al. discloses a method for enhancing the contour fidelity of printed images of two or more colors, which includes obtaining a digital representation of the color image and finding color separations of each color. Each color separation is enhanced by a single set of inverse symmetrical templates, the set including templates in which the second template is always the inverse of the first, and the third and fourth templates are always 180 degree rotations of the first two. The resulting smoothed color separations are recombined into an enhanced image without separation error.
U.S. Pat. No. 5,387,985 to Loce et al. discloses a method and apparatus for converting the resolution of bitmap images, and more specifically, to the use of a template matching process to alter the resolution of digital images for printing or similar methods of rendition. The present invention uses statistically generated templates, implemented using look-up tables, to improve document appearance upon output by converting from an original or input spatial resolution to an output spatial resolution that is device dependent, and where there is a non-integer relationship between the input and output resolutions. The resulting image signals may then be utilized to control a scanning beam where the beam varies in intensity and duration according to the pulses used to control it.
U.S. Pat. No. 5,579,445 to Loce et al discloses a method and apparatus for automating the design of morphological or template-based filters for print quality enhancement. A plurality of different phase, but same resolution, subsampled images are generated from training documents. Statistical data derived therefrom is then employed in an automated process to generate filters. The filters may be used for resolution enhancement and/or conversion of bitmap images. Furthermore, the statistical data is used to produce filters that are intended to not only optimize image structure, but image density as well.
U.S. Pat. No. 5,696,845 to Loce et al. discloses a method and apparatus for improving the appearance of printed documents, and more specifically, to the use of a template matching process to enhance the fast-scan resolution of digital images while maintaining raster resolution for printing. The invention uses multiple-bit per pixel, statistically generated templates, implemented using look-up tables, to improve document appearance by converting from a single-bit per pixel to N-bits per pixel, while preserving raster resolution of the printed output. The resulting N-bit per pixel image signals may be utilized to control a scanning beam where the beam varies in intensity and duration according to the pulses used to control it.
A number of the previously described patents and publications are summarized in Torrey Pines Research, Behind Hewlett-Packard""s Patent on Resolution Enhancement(trademark) Technology, (Becky Colgan ed., BIS CAP International, 1990) pp. 1-60, including concepts associated with resolution enhancement.
Robert P. Loce et al. in Facilitation of Optimal Binary Morphological Filter Design via Structuring Element Libraries and Design Constraints, Optical Engineering, Vol. 31, No. 5, May 1992, pp. 1008-1025, incorporated herein by reference, describes three approaches to reducing the computational burden associated with digital morphological filter design. Although the resulting filter is sub-optimal, imposition of the constraints in a suitable manner results in little loss of performance in return for design tractability.
Mathematical Morphology in Image Processing, pp. 43-90 (Edward R. Dougherty ed., Marcel Dekker 1992), hereby incorporated by reference, describes efficient design strategies for the optimal binary digital morphological filter. A sub-optimal design methodology is investigated for binary filters in order to facilitate a computationally manageable design.
Robert P. Loce and Edward R. Dougherty in Spatial Resolution Conversion Using Paired Increasing Operators. Enhancement and Restoration of Digital Documents, pp. 202-210, SPIE Optical Engineering Press, 1997, hereby incorporated by reference, discloses a paired-erosion-based-filter architecture for performing the general image mappings required for optimal spatial resolution conversion. One member of the pair is an antiextensive operator while the other is extensive.
All of the above cited references are hereby incorporated by reference for their teachings.
In accordance with the present invention, there is provided a method of processing digital image data to produce enhanced output images, which includes the steps of: selecting a target pixel location in the bitmap image; observing a set of pixels within a pixel observation window superimposed on the bitmap image, relative to the target pixel location; generating an index pointer as a function of the pixel set by rotating the pixel set about an angle in a multi-dimensional space; using the index pointer, looking-up a code that defines the characteristics of a signal that will be used to output the target pixel; and rotating the signal about the pixel set angle in a three dimensional space and outputting the rotated signal.
In accordance with another aspect of the present invention, there is provided an electronic printing machine, which includes a raster exposure device; and an enhancement filter, connected to the raster exposure device, for performing pixel resolution enhancement on a bitmap image input thereto so as to produce a series digital signals to drive the raster exposure device, wherein the digital signals. include a code that defines the characteristics of an output signal that will and an angle about which the output signal should be rotated in order to achieve pixel resolution enhancement.
In accordance with yet another aspect of the present invention, there is provided a method of reducing a number of entries stored in a look up table, wherein the look up table entries are associated with multiple output signals, including the steps of examining the look up table entries and the output signals, and reducing a number of output signals that will be generated based upon similarities between the look up table entries and the output signals.